#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include <unordered_map>

using namespace std;
/*HJJ QQ479287006
 *请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

 

示例 1：



输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：



输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//这个题的意思就是实现深拷贝
//虽然是这个意思但是 还有原地转换的方法 。就是后面插入一个一样的 然后拆分 例如
//原来是 1 2 3 4 -> 1 1 2 2 3 3 4 4
//第二种这两种写了一个小时了将近应该还多
Node *copyRandomList(Node *head) {

    if (head == nullptr)
        return head;

    //映射源节点和开启的节点
    unordered_map<Node *, Node *> mp;

    Node *headTmp = head;
    while (headTmp != nullptr) {
        Node *tempNode = new Node(headTmp->val);
        mp[headTmp] = tempNode;
        headTmp = headTmp->next;
    }

    //第二次遍历  链接random
    headTmp = head;

    while (headTmp != nullptr) {
        mp[headTmp]->next = mp[headTmp->next];
        //链接 随机节点
        mp[headTmp]->random = mp[headTmp->random];
        //
        headTmp = headTmp->next;

    }

    return mp[head];
}

////效率并不高
Node *copyRandomList2(Node *head) {


    //记录返回的指针
    Node *ret = nullptr;

    //复制节点到后面
    Node *headTmp = head;
    while (headTmp != nullptr) {
        Node *temp = new Node(headTmp->val);

        Node *nodeNext = headTmp->next;

        headTmp->next = temp;
        temp->next = nodeNext;

        headTmp = nodeNext;

    }
    ret = head->next;//获取返回指针

    //节点的拆分 1 1 2 2 3 3 4 4


    headTmp = head;//重置头
    //链接复制的random
    while (headTmp != nullptr) {

        Node *temp = headTmp->next->next;//获取下一个自己的节点

        if (headTmp->random != nullptr)
            headTmp->next->random = headTmp->random->next;


        headTmp = temp;//原始节点指针迁移

    }


    Node *retTemp = ret;//复制的头
    headTmp = head;
    while (headTmp != nullptr) {

        Node *temp = headTmp->next->next;//获取下一个自己的节点
        headTmp->next = temp;//链接原始节点

        if (temp != nullptr)
            retTemp->next = temp->next;//链接 拷贝节点
        // retTemp->random=temp->next->random;//链接random 是分开了 但是无法链接
        if (temp != nullptr)
            retTemp = temp->next;//拷贝节点指针迁移


        headTmp = temp;//原始节点指针迁移

    }


    return ret;

}

// 2023 .3.23 重新刷未果
Node *copyRandomList3(Node *head) {
    if (!head)
        return head;
    unordered_map<Node *, Node *> mp;
    auto temp = head;
    temp = temp->next;
    auto res = new Node(head->val);
    auto rt = res;
    while (temp->next != nullptr) {
        rt->next = new Node(temp->val);
        rt->random =
        mp[rt] = new Node(temp->random->val);
        rt = rt->next;
        temp = temp->next;

    }


}
